Two broad classes of methods can be used for the construction of low-density parity-check (LDPC) codes. One class is based on random graph constructions, while the other class is based on structured algebraic constructions. Random graph constructions can produce LDPC codes that approach the Shannon capacity.
LDPC graph constructions normally use a “Tanner graph,” which is a bi-partite graph including “variable” nodes representing the codeword bits, and “check” nodes representing the parity checks, where a variable node is connected to a check node by an edge if and only if the corresponding entry in the parity check matrix for the code is nonzero. Tanner graphs are well known.
Although LDPC codes based on highly random Tanner graph construction can closely approach the Shannon limit, those constructions are difficult to implement in hardware because the irregular connections between check and variable nodes in the Tanner graph of the code imply high complexity wiring. In actual implementations, more structured constructions are preferred because those provide practical wiring, and straightforward parallelism in the decoders.
Quasi-cyclic LDPC (QC LDPC) codes are structured graph constructions that use a parity check matrix which is partitioned into sub-matrices that have a circulant structure. Because the structured graph construction is practical to implement in hardware, QC LDPC codes are used in a variety communication networks, such as networks implemented according to the IEEE 802.16e, DVB-S2, and IEEE 802.11 standards.
For most applications, it is important to optimize decoding performance in a “water-fall” regime where the signal-to-noise ratio (SNR) is relatively low. However, for some applications, optimizing water-fall performance is not sufficient. One must also avoid “error floors” that are characteristic of many LDPC codes in higher SNR regimes. The error floor in the performance curve means that the decoding failure rate does not continue to decrease as the SNR increases. Eliminating or lowering error floors is particularly important for applications that require extreme reliability demands, including high density data storage, and high speed fiber-optic communication systems.
Generally, QC LDPC codes are constructed based on a wide variety of techniques, including finite geometries, finite fields, and combinatorial designs. Recently, there has also been great interest in a class of “convolutional,” or “spatially-coupled” codes, which are much more structured than the conventional random constructions, but have also been shown to closely approach the Shannon capacity, or even to achieve the Shannon capacity on a binary erasure channel (BEC). Those codes are significant here, because the codes can be implemented using quasi-cyclic constructions, and the codes should thus be able to achieve very good performance while retaining the practicality of other structured QC LDPC codes.
Error floor issues for LDPC codes that are decoded using belief propagation (BP) or related decoders are generally caused by “trapping sets.” A trapping set is a set of a small number of bits that reinforce each other in their incorrect beliefs. Trapping sets of bits are invariably arranged in clustered short cycles in a Tanner graph for the code. One way to remove the trapping sets is to design the Tanner graph so that clusters of short cycles do not exist. An alternative, and at least conceptually simpler approach is to design codes with larger girths. The “girth” of a code is the length of the shortest cycle in the Tanner graph. By removing short cycles, we remove potentially dangerous configurations of cycles, and hopefully lower the error floor. Unfortunately, there are no guarantees that the code with large girth, e.g., eight or greater, will have no trapping sets.
Therefore, there is a need in the art to provide a method for determining QC LDPC codes having no trapping sets.